package leetcode.editor.vscdev;
import java.util.*;
import leetcode.editor.utils.*;

public class lc654 {

    class Solution {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            // 调用递归
            return func(nums, 0, nums.length);
        }
        public TreeNode func(int[] nums, int left, int right){
            // 递归结束条件
            if (left == right) return null;
            // 找到最大值
            int max = nums[left];
            int index = left;
            for (int i = left; i < right; i++) {
                if (nums[i] > max){
                    max = nums[i];
                    index = i;
                }
            }
            // 以最大值为根节点 创建其左右子树
            TreeNode root = new TreeNode(max);
            root.left = func(nums, left, index);
            root.right = func(nums, index + 1, right);
            return root;
        }
    }
}
